package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/can-place-flowers/'>种花问题(Can Place Flowers)</a>
 * <p>假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。</p>
 * <p>给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：flowerbed = [1,0,0,0,1], n = 1
 *      输出：true
 *
 * 示例 2：
 *      输入：flowerbed = [1,0,0,0,1], n = 2
 *      输出：false
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= flowerbed.length <= 2 * 10^4</li>
 *     <li>flowerbed[i] 为 0 或 1</li>
 *     <li>flowerbed 中不存在相邻的两朵花</li>
 *     <li>0 <= n <= flowerbed.length</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/9 16:16
 */
public class LC0605CanPlaceFlowers_S {

    static class Solution {
        public boolean canPlaceFlowers(int[] flowerbed, int n) {
            if (n == 0) {
                return true;
            }
            // 偶数块地最多种植 n/2 朵花，奇数块地最多种植 n/2+1 朵花
            int length = flowerbed.length;
            if (((length + 1) >> 1) < n) {
                return false;
            }
            // 如果只有1块地
            if (length == 1) {
                return n == 1 && flowerbed[0] == 0;
            }
            int idx = 0;
            while (idx < length && n > 0) {
                if (flowerbed[idx] == 1) {
                    // 如果当前地有植物，下一块地无法种植。所以直接来到下下一块地
                    // 因为没有两块连续的 1。所以遇到 1，下一块一定为0
                    idx += 2;
                } else if (idx == flowerbed[length - 1] || flowerbed[idx + 1] == 0) {
                    // 如果来到最后一块地 或 当前地的下一块地没有植物。则当前地可种植。下一块地无法种植，还是跳两步
                    n--;
                    idx += 2;
                } else {
                    // 当前地为0，下一块为1。跳三步
                    idx += 3;
                }
            }
            return n <= 0;
        }

        public boolean canPlaceFlowers2(int[] flowerbed, int n) {
            if (n == 0) {
                return true;
            }
            // 偶数块地最多种植 n/2 朵花，奇数块地最多种植 n/2+1 朵花
            int length = flowerbed.length;
            if (((length + 1) >> 1) < n) {
                return false;
            }
            // 如果只有1块地
            if (length == 1) {
                return n == 1 && flowerbed[0] == 0;
            }
            int canPlaceFlowers = 0;
            for (int i = 0; i < length; i++) {
                if (flowerbed[i] == 0) {
                    if (i == 0) {
                        // 如果在第一块地。只有第二块可以无植物才可以种植
                        if (flowerbed[i + 1] == 0) {
                            canPlaceFlowers++;
                            flowerbed[i] = 1;
                        }
                    } else if (i == length - 1) {
                        // 如果在最后一块地。只有倒数第二块可以无植物才可以种植
                        if (flowerbed[i - 1] == 0) {
                            canPlaceFlowers++;
                        }
                    } else {
                        // 中间的地需要前一块和和一块都没有植物才可以种植
                        if (flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
                            canPlaceFlowers++;
                            flowerbed[i] = 1;
                        }
                    }
                    if (canPlaceFlowers >= n) {
                        return true;
                    }
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.canPlaceFlowers(new int[]{1, 0, 0, 0, 1}, 1));
        System.out.println(solution.canPlaceFlowers(new int[]{1, 0, 0, 0, 1}, 2));
    }
}
